package LeetCode._01算法入门.day05双指针;

import org.junit.Test;

import java.util.Stack;

/**
 * @author 挚爱之夕
 * @date 2022-02-24 - 02 - 24 - 16:47
 * @Description 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
 * @Version 1.0
 */
public class _19删除链表的倒数第N个节点 {
    //0->1->2->3->4 删除非头结点
    static ListNode head1;
    static int n1 = 2;
    //1->2 删除头节点
    static ListNode head2;
    static int n2 = 2;
    static {
        head1 = new ListNode(0);
        ListNode listNode1 = new ListNode(1);
        head1.next = listNode1;
        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2;
        ListNode listNode3 = new ListNode(3);
        listNode2.next = listNode3;
        listNode3.next = new ListNode(4);

        head2 = new ListNode(1, new ListNode(2));
    }
    @Test
    public void solve(){
        ListNode res = removeNthFromEnd(head1, n1);
        System.out.println(res);//0->1->2->4

        ListNode res1 = removeNthFromEnd(head2, n2);
        System.out.println(res1);//2
    }
    //by em 双指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = head;
        ListNode right = head;
        //两个节点保持n的间隔
        for(int i = 0; i < n; i++){
            right = right.next;
        }

        if(right == null){//删除头节点(如果n不超过链表长度)，并返回
            if(head != null)
                head = head.next;
            return head;
        }

        while(right.next != null){
            right = right.next;
            pre = pre.next;
        }
        //此时pre是删除节点的前一个节点
        pre.next = pre.next.next;
        return head;
    }
    /*官方思路*/
    //使用栈 太慢了
    public ListNode removeNthFromEnd1(ListNode head, int n) {

        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //找到删除节点的前一个节点
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        //删除头节点(如果n不超过链表长度)，并返回
        if(stack.isEmpty()){
            if(head == null)
                return null;
            else
                return head.next;
        }
        //删除节点的前一个节点
        ListNode pre = stack.pop();
        pre.next = pre.next.next;

        return head;
    }
}
